package com.practice.sequence;

/**
 * Find kth element in a sequence. See Selection Algorithm.
 *
 */
public class FindKth {
	public int find(int[] a, int k) {
		return find(a, 0, a.length-1, k);
	}
	
	private int find(int[] a, int left, int right, int k) {
		int i = left + 1;
		int r = right;
		while (i <= r) {
			if (a[i] > a[left]) {
				int t = a[r];
				a[r] = a[i];
				a[i] = t;
				r--;
			}
			else {
				i++;
			}
		}
		
		int t = a[r];
		a[r] = a[left];
		a[left] = t;
		
		if (k == r-left+1) return a[r];
		if (k < r-left+1) {
			return find(a, left, r, k);
		}
		else {
			return find(a, r+1, right, k-r+left-1);
		}
	}
}
